home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1993 July / InfoMagic USENET CD-ROM July 1993.ISO / sources / misc / volume6 / lookup.c++ < prev    next >
Encoding:
Text File  |  1989-03-04  |  10.3 KB  |  398 lines

  1. Newsgroups: comp.sources.misc
  2. From: allbery@uunet.UU.NET (Brandon S. Allbery - comp.sources.misc)
  3. Subject: v06i043: lookup -- look up commands in table
  4. Keywords: c++, lookup table, linear and binary search
  5. Reply-To: geac!rae (Reid Ellis)
  6. Organization: T'nir Software
  7.  
  8. Posting-number: Volume 6, Issue 43
  9. Submitted-by: rae@b.UUCP (Reid Ellis)
  10. Archive-name: lookup.c++
  11.  
  12.  
  13. The following shar implements a lookup table in C++.  Two alternate
  14. algorithms are presented, binary and linear search, in the files lookup.c
  15. and lookup2.c, respectively.  See the README file for more details.  Don't
  16. worry -- there's an "exit" before my .signature.
  17.  
  18.                     Reid
  19.  
  20. #! /bin/sh
  21. # This is a shell archive.  Remove anything before this line, then unpack
  22. # it by saving it into a file and typing "sh file".  To overwrite existing
  23. # files, type "sh file -c".  You can also feed this as standard input via
  24. # unshar, or by typing "sh <file", e.g..  If this archive is complete, you
  25. # will see the following message at the end:
  26. #        "End of shell archive."
  27. # Contents:  Makefile README lookup.c lookup.h lookup2.c test.c
  28. #   testcmd.c testhelp.c
  29. # Wrapped by rae@geaclib on Tue Feb  7 05:37:45 1989
  30. PATH=/bin:/usr/bin:/usr/ucb ; export PATH
  31. if test -f Makefile -a "${1}" != "-c" ; then 
  32.   echo shar: Will not over-write existing file \"Makefile\"
  33. else
  34. echo shar: Extracting \"Makefile\" \(419 characters\)
  35. sed "s/^X//" >Makefile <<'END_OF_Makefile'
  36. XCC = CC -c -I/usr/include/CC
  37. XLD = CC
  38. X
  39. X.c.o:
  40. X    $(CC) $(CFLAGS) $<
  41. X
  42. X# lookup2 does a linear search -- good for unsorted table
  43. X# lookup  does a binary search -- good for a sorted table
  44. XOBJ = test.o lookup2.o testcmd.o testhelp.o
  45. X#OBJ = test.o lookup.o testcmd.o testhelp.o
  46. XTARG = tt
  47. X
  48. X$(TARG): $(OBJ)
  49. X    $(LD) -o $(TARG) $(OBJ) $(LDFLAGS)
  50. X    @strip $(TARG)
  51. X
  52. Xlookup.o lookup2.o : lookup.h
  53. Xtest.o : lookup.h
  54. Xtesthelp.o : lookup.h
  55. END_OF_Makefile
  56. if test 419 -ne `wc -c <Makefile`; then
  57.     echo shar: \"Makefile\" unpacked with wrong size!
  58. fi
  59. # end of overwriting check
  60. fi
  61. if test -f README -a "${1}" != "-c" ; then 
  62.   echo shar: Will not over-write existing file \"README\"
  63. else
  64. echo shar: Extracting \"README\" \(2827 characters\)
  65. sed "s/^X//" >README <<'END_OF_README'
  66. XDESCRIPTION
  67. X
  68. XUsing the files lookup.c [or lookup2.c] and lookup.h, you can easily maintain
  69. Xa command lookup table.  The table must be of type "entry *", and you can see
  70. Xin the example code [test.c, testcmd.c, testhelp.c] that I used an aggreagate
  71. Xarray of the form:
  72. X
  73. Xentry list[] = { ... };
  74. X
  75. XThe first "entry" in the list must have a count and a pointer to an error
  76. Xfunction.  If you have no error function, create a null function, which
  77. Xdoes nothing, and use a pointer to it.  Since the number occupies the
  78. Xposition of a char*, you have to cast it to such.  i.e., if you have
  79. X#define'd NUM to the number of elements, you would say
  80. X
  81. Xentry list[] = {
  82. X  (char *)NUM, &err,
  83. X  ...
  84. X  };
  85. X
  86. Xwhere err is the error-handling function.  err would be called when a string
  87. Xnot in the list is referenced.
  88. X
  89. XNow, the list is not the object that does the work.  Another object, of class
  90. X"lookup" is initialized with a pointer to an "entry *".  e.g., given the
  91. Xabove example, you could say:
  92. X
  93. Xlookup cmd(list);
  94. X
  95. XThereafter, to retrieve the function pointer desired, you simply reference
  96. X"cmd" with a string:
  97. X
  98. Xint (*proc)(const char *);
  99. Xproc=cmd["query"];
  100. X
  101. XThis would cause "proc" to point to the function associated with the
  102. Xword "query", if any; otherwise, it would point to the error function,
  103. Xwhich we designated above to be "err".  Now you can happily dereference the
  104. Xpointer and pass it a "const char *":
  105. X
  106. Xproc("testing");
  107. X
  108. XNow note that you can do both of these at once:
  109. X
  110. Xcmd["query"]("Testing");
  111. X
  112. XIsn't that special?
  113. X
  114. XThe only difference between lookup.c and lookup2.c is the implementation.
  115. XEach gives you an advantage.  If your list of names is sorted, use
  116. Xlookup.c since it uses a binary search.  Obviously, if they are not
  117. Xin any order, a binary search will not work, so lookup2.c just does
  118. Xa linear search.  This is the only difference between the two.
  119. X
  120. X
  121. XARGUMENT TYPE
  122. X
  123. XAll of the function pointers in the "entry" list must take the same
  124. Xargument[s], if any, and return the same value type.  I haven't built
  125. Xany elegant macros, but there are #defines in "lookup.h" to handle both
  126. Xof these problems in a less than elegant manner.
  127. X
  128. XThe two macros ARG_TYPE and RET_TYPE define the argument type and value
  129. Xvalue returned by the function pointers.  Just change these to handle whatever
  130. Xtypes you like.
  131. X
  132. X
  133. XCAVEATS
  134. X
  135. XThis is one of my first attempts at C++;  I hope you find it useful.  If
  136. Xyou make any major modifications, or even more importantly, if you find any
  137. Xbugs, please let me know so I can fix my source and post the patches for
  138. Xone and all.
  139. X
  140. X
  141. XCOPYRIGHT
  142. X
  143. XI the author hereby place this code in the public domain.  Make enough
  144. Xmoney to buy Canada and hire me as Prime Minister!
  145. X
  146. X
  147. XAUTHOR
  148. X
  149. XReid Ellis
  150. X176 Brookbanks Drive
  151. XDon Mills, Ontario
  152. XM3A 2T5
  153. XCANADA
  154. X+1 416 446 1644
  155. Xrae@geaclib.uucp if you're lucky, or else geaclib!rae@geac.uucp
  156. END_OF_README
  157. if test 2827 -ne `wc -c <README`; then
  158.     echo shar: \"README\" unpacked with wrong size!
  159. fi
  160. # end of overwriting check
  161. fi
  162. if test -f lookup.c -a "${1}" != "-c" ; then 
  163.   echo shar: Will not over-write existing file \"lookup.c\"
  164. else
  165. echo shar: Extracting \"lookup.c\" \(652 characters\)
  166. sed "s/^X//" >lookup.c <<'END_OF_lookup.c'
  167. X#include <stream.h>
  168. X#include <string.h>
  169. X#include "lookup.h"
  170. X
  171. Xproc lookup::operator[](const char *str)
  172. X  {
  173. X  int n;
  174. X  entry
  175. X    *upper = table + max - 1,
  176. X    *lower = table,
  177. X    *mid = lower + (upper-lower)/2;
  178. X
  179. X for(n=1; n && upper - lower > 1; )
  180. X    {
  181. X    n = strcmp(str, mid->name);
  182. X    if(n == 0)
  183. X      upper = lower = mid;
  184. X    else
  185. X      {
  186. X      if(n < 0) upper = mid;
  187. X      else      lower = mid;
  188. X      mid = lower + (upper - lower)/2;
  189. X      }
  190. X    }
  191. X
  192. X  if(n < 0) n = strcmp(str, mid->name);
  193. X  else if(n > 0)
  194. X    {
  195. X    mid = upper;
  196. X    n = strcmp(str, mid->name);
  197. X    }
  198. X
  199. X  if(n) return dflt;   // not in table
  200. X  else  return mid->f; // found it
  201. X  }
  202. END_OF_lookup.c
  203. if test 652 -ne `wc -c <lookup.c`; then
  204.     echo shar: \"lookup.c\" unpacked with wrong size!
  205. fi
  206. # end of overwriting check
  207. fi
  208. if test -f lookup.h -a "${1}" != "-c" ; then 
  209.   echo shar: Will not over-write existing file \"lookup.h\"
  210. else
  211. echo shar: Extracting \"lookup.h\" \(392 characters\)
  212. sed "s/^X//" >lookup.h <<'END_OF_lookup.h'
  213. X#ifndef LOOKUPH
  214. X#define LOOKUPH
  215. X
  216. X#define ARG_TYPE const char *
  217. X#define RET_TYPE int
  218. X
  219. Xtypedef RET_TYPE (*proc)(ARG_TYPE);
  220. X
  221. Xstruct entry {
  222. X    const char *name;
  223. X    proc f;
  224. X    };
  225. X
  226. Xclass lookup {
  227. X    entry *table;
  228. X    proc dflt;
  229. X    int max;
  230. Xpublic:
  231. X    lookup(entry *t) {
  232. X        dflt = t->f;
  233. X        max = int(t->name);
  234. X        table = t + 1;
  235. X        }
  236. X    // This really does take a const char *
  237. X    proc operator[](const char *);
  238. X    };
  239. X#endif
  240. END_OF_lookup.h
  241. if test 392 -ne `wc -c <lookup.h`; then
  242.     echo shar: \"lookup.h\" unpacked with wrong size!
  243. fi
  244. # end of overwriting check
  245. fi
  246. if test -f lookup2.c -a "${1}" != "-c" ; then 
  247.   echo shar: Will not over-write existing file \"lookup2.c\"
  248. else
  249. echo shar: Extracting \"lookup2.c\" \(263 characters\)
  250. sed "s/^X//" >lookup2.c <<'END_OF_lookup2.c'
  251. X#include <stream.h>
  252. X#include <string.h>
  253. X#include "lookup.h"
  254. X
  255. Xproc lookup::operator[](const char *str)
  256. X  {
  257. X  entry *t=table;
  258. X
  259. X  for(; t-table < max; t++)
  260. X    if(!strcmp(t->name, str))
  261. X      break;
  262. X
  263. X  if(t-table<max) return t->f;
  264. X  else            return dflt;
  265. X  }
  266. END_OF_lookup2.c
  267. if test 263 -ne `wc -c <lookup2.c`; then
  268.     echo shar: \"lookup2.c\" unpacked with wrong size!
  269. fi
  270. # end of overwriting check
  271. fi
  272. if test -f test.c -a "${1}" != "-c" ; then 
  273.   echo shar: Will not over-write existing file \"test.c\"
  274. else
  275. echo shar: Extracting \"test.c\" \(882 characters\)
  276. sed "s/^X//" >test.c <<'END_OF_test.c'
  277. X#include <stream.h>
  278. X#include <string.h>
  279. X#include "lookup.h"
  280. X
  281. Xextern RET_TYPE
  282. X    a(ARG_TYPE),
  283. X    b(ARG_TYPE),
  284. X    c(ARG_TYPE),
  285. X    help(ARG_TYPE),
  286. X    oops(ARG_TYPE);
  287. X
  288. Xentry list[] = {
  289. X  (char *)4, &oops,
  290. X  "acmd", &a,
  291. X  "bcmd", &b,
  292. X  "c", &c,
  293. X  "help", &help,
  294. X  };
  295. X
  296. Xint main(int argc, char *argv[])
  297. X  {
  298. X  char *progname = argv[0];
  299. X  lookup command(list);
  300. X  char word[200]; // of type ARG_TYPE
  301. X  int i;
  302. X
  303. X  argc--; // to shut up CC
  304. X
  305. X  while(cout << "% ", cin >> word && strcmp(word, "quit"))
  306. X    {
  307. X
  308. X    // Note that in the next statement, we are in
  309. X    // fact saying command[const char *](ARG_TYPE)
  310. X    // In this case, ARG_TYPE *is* const char *, so we 
  311. X    // are just passing the same thing to both [] and ().
  312. X
  313. X    if(i = command[word](word))
  314. X      {
  315. X      // the function returned a non-zero result
  316. X      cerr << form("%s: %s returned %d\n", progname, word, i);
  317. X      }
  318. X    }
  319. X  return 0;
  320. X  }
  321. END_OF_test.c
  322. if test 882 -ne `wc -c <test.c`; then
  323.     echo shar: \"test.c\" unpacked with wrong size!
  324. fi
  325. # end of overwriting check
  326. fi
  327. if test -f testcmd.c -a "${1}" != "-c" ; then 
  328.   echo shar: Will not over-write existing file \"testcmd.c\"
  329. else
  330. echo shar: Extracting \"testcmd.c\" \(328 characters\)
  331. sed "s/^X//" >testcmd.c <<'END_OF_testcmd.c'
  332. X#include <stream.h>
  333. X
  334. Xint a(const char *s)
  335. X  {
  336. X  cout << form("a: %s\n", s);
  337. X  return 0;
  338. X  }
  339. X
  340. Xint b(const char *s)
  341. X  {
  342. X  cout << form("b: %s\n", s);
  343. X  return 0;
  344. X  }
  345. X
  346. Xint c(const char *s)
  347. X  {
  348. X  cout << form("c: %s\n", s);
  349. X  return 0;
  350. X  }
  351. X
  352. Xint oops(const char *s)
  353. X  {
  354. X  cout << form("command %s unavailable\n", s);
  355. X  return 0;
  356. X  }
  357. END_OF_testcmd.c
  358. if test 328 -ne `wc -c <testcmd.c`; then
  359.     echo shar: \"testcmd.c\" unpacked with wrong size!
  360. fi
  361. # end of overwriting check
  362. fi
  363. if test -f testhelp.c -a "${1}" != "-c" ; then 
  364.   echo shar: Will not over-write existing file \"testhelp.c\"
  365. else
  366. echo shar: Extracting \"testhelp.c\" \(341 characters\)
  367. sed "s/^X//" >testhelp.c <<'END_OF_testhelp.c'
  368. X#include <stream.h>
  369. X#include "lookup.h"
  370. X
  371. Xextern entry list[];
  372. X
  373. Xint help(const char *s)
  374. X  {
  375. X  entry *t = list;
  376. X
  377. X  (void) s; // "use" s so that CC won't complain
  378. X  cout << "Available commands:\n\n";
  379. X  cout << "quit\t";
  380. X
  381. X  for(int max=1+int((t++)->name); t-list < max; t++)
  382. X    cout << form("%s\t", t->name);
  383. X
  384. X  cout.put('\n');
  385. X  return 0;
  386. X  }
  387. END_OF_testhelp.c
  388. if test 341 -ne `wc -c <testhelp.c`; then
  389.     echo shar: \"testhelp.c\" unpacked with wrong size!
  390. fi
  391. # end of overwriting check
  392. fi
  393. echo shar: End of shell archive.
  394. exit 0
  395. -- 
  396. Reid Ellis, geaclib!rae@geac.uucp, rae@geaclib.uucp [if you're lucky]
  397.  
  398.